/**
 * @projectName leetode
 * @package cn.leetcode
 * @className cn.leetcode.t222
 * @copyright Copyright 2020 Thunisoft, Inc All rights reserved.
 */
package cn.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * t222
 * @description
 * @author fei
 * @date 2025/9/8 18:10
 * @version 1.0
 */
/*
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

示例 1：


输入：root = [1,2,3,4,5,6]
输出：6
示例 2：

输入：root = []
输出：0
示例 3：

输入：root = [1]
输出：1
 */
public class t222 {
    public int countNodes(TreeNode root) {
        /*
        int ans = 0;
        if (root == null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            ans+=size;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return ans;
         */
        if (root == null){
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftCount = 0, rightCount = 0;
        while (left != null){
            left=left.left;
            leftCount++;
        }
        while (right != null){
            right=right.right;
            rightCount++;
        }
        if (leftCount == rightCount){
            return (1 << leftCount) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
